package algorithm.monotonousStack;


import java.util.Stack;

//一个正整数数组的所有子数组中“最小值”乘“子数组的和”的最大值
public class AllTimesMinToMax {

    public static int maxValue(int[] arr){
        long max = Long.MIN_VALUE;
        long[] sums = new long[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sums[i] = i == 0? arr[i] : sums[i - 1] + arr[i];
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while(!stack.isEmpty() && arr[stack.peek()] >= arr[i]){
                Integer pop = stack.pop();
                if(!stack.isEmpty())
                    max = Math.max(max, (sums[i - 1] - sums[stack.peek()]) * arr[pop]);
                else
                    max = Math.max(max, (sums[i - 1] * arr[pop]));
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            Integer pop = stack.pop();
            if(!stack.isEmpty())
                max = Math.max(max, (sums[arr.length - 1] - sums[stack.peek()]) * arr[pop]);
            else
                max = Math.max(max, sums[arr.length - 1] * arr[pop]);
        }

        return (int)(max % (1000000007));
    }

    public static int maxValue2(int[] arr){
        long max = Long.MIN_VALUE;
        long[] sums = new long[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sums[i] = i == 0? arr[i] : sums[i - 1] + arr[i];
        }

        int[] st = new int[arr.length];
        int last = -1;
        for (int i = 0; i < arr.length; i++) {
            while(last != -1 && arr[st[last]] >= arr[i]){
                Integer pop = st[last];
                last--;
                if(last != -1)
                    max = Math.max(max, (sums[i - 1] - sums[st[last]]) * arr[pop]);
                else
                    max = Math.max(max, (sums[i - 1] * arr[pop]));
            }
            last++;
            st[last] = i;
        }

        while(last != -1){
            Integer pop = st[last];
            last--;
            if(last != -1)
                max = Math.max(max, (sums[arr.length - 1] - sums[st[last]]) * arr[pop]);
            else
                max = Math.max(max, sums[arr.length - 1] * arr[pop]);
        }

        return (int)(max % 1000000007);
    }

    public static void main(String[] args) {
//        int[] arr = {2,3,3,1,2};
//        int[] arr2 = {1,2,3,2};
//        int i = maxValue2(arr);
//        System.out.println(i);



//        long s =(k % 1000000007);
//        System.out.println(s2);

//        double d = 0b11.1;
    }
}
